package com.leetcode.algorithm.y22.m06;

/**
 * 69. x 的平方根
 * 
 * https://leetcode.cn/problems/sqrtx/
 * 
 * @author jie.deng
 *
 */
public class Question0069Solution01 {

	/**
	 * 69. x 的平方根
	 * 
	 * 实现 int sqrt(int x) 函数。
	 * 
	 * 计算并返回 x 的平方根，其中 x 是非负整数。
	 * 
	 * 由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
	 * 
	 * 示例 1:
	 * 
	 * 输入: 4 输出: 2 示例 2:
	 * 
	 * 输入: 8 输出: 2 说明: 8 的平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
	 * 
	 * @param x
	 * @return
	 */
	public int mySqrt(int x) {
		if (x == 0 || x == 1) {
			return x;
		}
		int left = 1;
		int right = x;
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			long mul = (long) mid * mid;
			if (mul == x) {
				return mid;
			} else if (mul < x) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return right - 1;
	}

}
